RT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<stack>

using namespace std;


//class Solution {
//public:
//    void swap(string& s, size_t front, size_t last)
//    {
//        while (front < last)
//        {
//            std::swap(s[front], s[last]);
//            front++;
//            last--;
//        }
//    }
//    string reverseWords(string s) {
//
//        size_t pos = s.find(' ');
//        if (pos == string::npos)
//        {
//            swap(s, 0, s.size() - 1);
//            return s;
//        }
//        size_t front = 0;
//        size_t last = pos - 1;
//        swap(s, front, last);
//
//        front = pos + 1;
//        pos = s.find(' ', pos + 1);
//        while (pos != string::npos)
//        {
//            last = pos - 1;
//            swap(s, front, last);
//
//            front = pos + 1;
//            pos = s.find(' ', pos + 1);
//        }
//        last = s.size() - 1;
//        swap(s, front, last);
//        return s;
//    }
//};

////using namespace std;
//class Solution {
//public:
//    vector<vector<int>> generate(int numRows) {
//        vector<vector<int>> vv;
//        int i = 0;
//        int j = 0;
//
//        vv.resize(numRows);
//
//        //初始化第一个值和最后一个值
//        for (i = 0; i < numRows; i++)
//        {
//            vv[i].resize(i + 1, 0);
//
//            vv[i][0] = 1;
//            vv[i][vv[i].size() - 1] = 1;
//        }
//
//        //计算
//        for (i = 0; i < numRows; i++)
//        {
//            for (j = 0; j < vv[i].size(); j++)
//            {
//                if (vv[i][j] == 0)
//                    vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
//            }
//        }
//
//        return vv;
//    }
//};

//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        size_t pos = 0;
//        size_t cur = 0;
//        while (cur < nums.size())
//        {
//            if (nums[pos] == nums[cur])
//            {
//                cur++;
//            }
//            else
//            {
//                pos++;
//                nums[pos] = nums[cur];
//                cur++;
//            }
//        }
//        return pos + 1;
//    }
//};


//#include<algorithm>
//class Solution {
//public:
//    int MoreThanHalfNum_Solution(vector<int> numbers) {
//        if (numbers.size() == 1)
//            return numbers[0];
//
//        sort(numbers.begin(), numbers.end());
//        int size = numbers.size() / 2;
//
//        int count = 0;
//        int pos = 0;
//        int cur = 1;
//        while (pos < numbers.size())
//        {
//            if (numbers[pos] == numbers[cur])
//            {
//                cur++;
//                count++;
//                if (count >= size)
//                    return numbers[pos];
//            }
//            else
//            {
//                if (numbers[pos] != numbers[pos - 1])
//                    count = 1;
//                pos = cur;
//                cur++;
//            }
//        }
//        return 0;
//    }
//};


#include<algorithm>

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int prev = 0;
        int cur = 1;
        int next = 2;

        if (nums.size() == 1)
            return nums[0];

        while (next < nums.size())
        {
            if (nums[prev] != nums[cur])
                return nums[prev];
            else
            {
                prev += 3;
                cur += 3;
                next += 3;
            }
        }
        if (prev = nums.size() - 1)
            return nums[prev];
        return -1;
    }
};

int main()
{
    Solution s;

    //stack<int>* st = new stack<int>;
    //st->push(1);
	return 0;
}
